package algo;

/**
 * @description:
 * =============================
 * 递归法打印全排列
 *
 * 例如 123的全排列有 123 132 213 231 312 321
 * 我们可以用递归的思想，将问题简化
 * 当存在n个数据 array[n]时
 * 第一个元素可以是n中的任意一个元素，我们采用一个函数swap 将第一个数与后面数交换位置，就可以得到第一个位置不同的情况。
 * 递归调用 printArragne（int [ ] array , int k , int n ）方法
 * array为需要全排列的数组，k为当前需要打印的起始地址，n为元素个数。
 * 而递归的出口就是n==k的时候，当需要打印的地址等于元素个数时候就结束
 * k<n时，则循环交换k与后面所有的数
 * 循环里面则递归调用printArrange以便从数组下标0到n-1全部递归输出
 * 交换完后记得还要交换回去
 * =============================
 * @author: walt-zhong
 * @createDate: 2021/3/10
 */
public class Arrange {

    public static void arrange(int []arr,int k,int n){
        if(k == n){
            for(int i = 0;i<arr.length;i++){
                System.out.print(arr[i]);
            }
            System.out.print(",");
        }else{
            for(int j = k;j<n+1;j++){
                swap(arr,k,j);
                arrange(arr,k+1,n);
                swap(arr,k,j);
            }
        }

    }


    public static void swap(int [] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String args[]){
        int [] arr = {1,2,3};
        arrange(arr,0,arr.length-1);

    }
}
